package DisjointSetUnion;

public class NumberOfIslands {

    public static int numIslands(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        build(n, m, board);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '1') {
                    // 上面存在且是土地
                    if (j > 0 && board[i][j - 1] == '1') {
                        union(i, j, i, j - 1);
                    }

                    // 左边存在且是土地
                    if (i > 0 && board[i - 1][j] == '1') {
                        union(i, j, i - 1, j);
                    }
                }
            }
        }

        return sets;
    }

    private static void union(int i, int j, int i1, int j1) {
        father[find(index(i, j))] = find(index(i1, j1));
    }

    /**
     * @param index 元素下标
     * @return 鼻祖节点
     */
    private static int find(int index) {
        if (index != father[index]) {
            // 扁平化
            father[index] = find(father[index]);
        }
        return father[index];
    }

    public final static int max_n = 10_0001;
    public static int[] father = new int[max_n];
    public static int cols;
    public static int sets;

    public static void build(int n, int m, char[][] board) {
        cols = m;
        sets = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0, index; j < m; j++) {
                if (board[i][j] == '1') {
                    index = index(i, 1);
                    father[index] = index;
                    sets++;
                }
            }
        }
    }

    private static int index(int i, int j) {
        return i * cols + j;
    }
}
